// 2025/3/30
// https://leetcode.cn/problems/partition-labels/description/?envType=study-plan-v2&envId=top-100-liked
// 划分字母区间

class Solution {
    public:
        vector<int> partitionLabels(string s) {
            int n = s.size(), words = 0;
            // 长度/字母
            stack<pair<int, int>> strs;
            for(int i = 0; i < n; i++)
            {
                int tmp = (1 << (s[i] - 'a'));
                if(words & tmp)
                {
                    pair<int, int> pr = {1, tmp};
                    while(!strs.empty() && !(strs.top().second & tmp))
                    {
                        pr.first += strs.top().first;
                        pr.second |= strs.top().second;
                        strs.pop();
                    }
                    if(!strs.empty())
                    {
                        strs.top().first += pr.first;
                        strs.top().second |= pr.second;
                    }
                    else
                    {
                        strs.push(pr);
                    }
                }
                else
                {
                    strs.emplace(1, tmp);
                    words |= tmp;
                }
            }
            int m = strs.size();
            vector<int> ans(m, 0);
            for(int end = m - 1; end >= 0; end--)
            {
                ans[end] = strs.top().first;
                strs.pop();
            }
            return ans;
        }
    };